package arrays.二分查找;

//leetcode submit region begin(Prohibit modification and deletion)
class 在D天内送达包裹的能力1011 {
    public int shipWithinDays(int[] weights, int days) {
        //左右边界
        int left = 0;
        int right = 1;
        for (int weight : weights) {
            left = Math.max(left, weight);
            right += weight;
        }
        //在运力为x的情况下运送玩所需要的天数f(x)的结果，小于等于days
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (cal(weights, mid) <= days) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

    //
    public int cal(int[] weights, int mid) {
        int days = 0;
        for (int i = 0; i < weights.length; ) {
            int cap = mid;
            while (i < weights.length) {
                if (cap < weights[i]) {
                    break;
                }
                else{
                    cap -= weights[i];
                }
                i++;
            }
            days++;
        }
        return days;
    }
}
//leetcode submit region end(Prohibit modification and deletion)
